Defining a method for managing 1609.2 Certificate Signing Request (CSR) or other anonymous certificates for the Vehicle Infrastructure Integration (VII) system is a very difficult, complex, and multi-faceted technical challenge. No method proposed to date has completely satisfied all design goals. Each offers a different balance of competing and intricately interrelated objectives, which include vehicle privacy, system security, system scalability, system robustness, vehicle segment maintenance, low complexity, practical implementation and ubiquitous operation.
Various categories of approaches for the management of anonymous keys and certificates are known. One such category includes combinatorial certificate schemes that are shared-key approaches where each vehicle uses a small number of keys and certificates that are drawn randomly from a shared pool of keys and certificates. The keys in the pool can be created by a key-generation algorithm. Privacy is achieved because each key and certificate is shared by many vehicles. However, the balance among scalability, privacy, and performance in this category is limited.
Another category is a short-lived, unlinked certificate scheme in which each vehicle is assigned a large number of unique keys. Privacy is achieved because each vehicle can use one out of a large number of certificates at any time.
The basic combinatorial anonymous certificate schemes, or basic combinatorial: schemes, achieve privacy by distributing the same public-private key pair and its associated certificate to a sufficiently large number of vehicles. Thus, any activity related to a particular key and certificate cannot be traced to a single vehicle because the number of vehicles potentially originating such activity is very large. A short description is presented of the basic combinatorial scheme organized into the following three phases: key generation, key distribution, and key revocation and update.
Key Generation: The Certificate Authority (CA) creates a pool of N uniformly and independently distributed triples, each triple containing a public key, a secret private key, and an associated certificate.
Key Distribution: Every vehicle will be given a small number (n) of keys, and their associated certificates chosen randomly and independently from the pool.
Key Revocation and Replacement: Keys and certificates could be used in malicious activities. Once a certificate is detected to be involved in malicious activities, the CA will revoke the certificate. The CA can revoke a certificate by posting it on a public certificate revocation list (CRL) which will be distributed to all vehicles and other entities that need to communicate with vehicles and therefore will need to verify 1609.2 certificates. Any communication signed using a revoked key will be disregarded.
When a certificate C is revoked, each vehicle that shares C will eventually request from the CA a new key pair and its certificate to replace the revoked certificate. The CA uses the number of rekey requests from each vehicle to determine whether a vehicle is a suspect in malicious activities and whether the vehicle should continue to receive new anonymous keys and certificates. In particular, the CA will only give new anonymous keys and certificates to a vehicle that has not requested more than b keys, where b is referred to as the rekey threshold. When all anonymous certificates on a vehicle have been revoked and the vehicle is no longer allowed by the CA to receive new anonymous certificates, the vehicle will need to be taken to service stations for further investigation and to gain re-authorization before it is allowed to receive new certificates again.
The basic combinatorial schemes replace revoked certificates by revoking each misbehaving key k immediately upon detection and use the same new key k′ to replace the revoked certificate k on every vehicle that requests a replacement certificate for k. In the alternative, the revoked certificates can be replaced by revoking g>1 certificates at a time. The CA creates g replacement keys (and their associated certificates) to replace the g revoked keys. Each vehicle requesting for rekey will be given a key randomly drawn with probability p from the set of newly created replacement keys and with probability 1−p from entire pool of N keys.
Techniques are known to associate the anonymous certificates assigned to a vehicle with vehicle-specific information (e.g., the VIN number) so that the on-board equipment (OBE) will not function when it is moved to a different vehicle.
The certificate revocation and replacement methods in the basic combinatorial schemes have limitations. For example, if the same certificate is used to replace a revoked key on all vehicles that have this revoked key, an attacker can repeat its malicious activity indefinitely without being caught as follows. First, a vehicle sends a maliciously prepared message using a given key k. The VII system detects this message and key k is revoked. At this point, it is hard to detect which vehicle generated the maliciously prepared message as several vehicles were assigned key k and thus any one of them could have potentially acted maliciously. Later, all vehicles that previously shared key k update this key and receive a new key k′. Now, the attacker continues its malicious activity using the new key k′, thus forcing this new key to be revoked again. This loop might continue indefinitely without the VII system detecting which vehicle is acting maliciously.
In addition, the method in the basic combinatorial schemes for revoking g>1 certificates at a time and giving each requesting vehicle randomly selected certificates will result in unpredictable (uncontrollable) distributions of certificates among vehicles This means that the privacy, scalability, and performance of the certificate management system will become unknown and unmanageable over time.
The main operations in the anonymous certificate management process are 1) testing, 2) initialization, 3) selection and rotation, and 4) revocation and replacement of anonymous keys and certificates. Testing of anonymous keys and certificates can be performed by both vehicle suppliers and vehicle original equipment manufacturers (OEMs) to ensure the correct functioning of the key and certificate generation software and hardware components.
Initialization of anonymous keys and certificates involves the interaction between vehicles, vehicle dealers, and vehicle OEMs to allow vehicles to obtain their initial sets of live anonymous keys and certificates. Once a vehicle is initialized with its long-lasting keys and certificates, such as the 1609.2 CSR certificates, the vehicle can use these long-lasting keys and certificates to acquire initial anonymous keys and certificates in the same manner as it will acquire subsequent anonymous keys and certificates.
Selection and rotation of anonymous keys and certificates includes procedures used by each vehicle to select the anonymous keys and certificates to use and to decide how and when to rotate (change) the anonymous certificates each vehicle uses.
Revocation and replacement of anonymous keys and certificates determines which anonymous certificates should be revoked, revoking these certificates from the vehicles and the VII system, and providing new keys and certificates to replace the revoked keys and certificates on the vehicles. However, certificate revocation and replacement methods in the basic combinatorial certificate schemes have several crucial limitations that need to be overcome. First, they cannot support a moderate to high number of attackers. Second, they will result in unpredictable and uncontrollable probability distributions of certificates among vehicles, resulting in unpredictable and uncontrollable system scalability and performance. Third, they are missing some necessary methods to ensure the continuous operation of the certificate management system. For example, they use a fixed rekey threshold to determine which vehicles should no longer be allowed to receive new anonymous certificates, but do not provide a method for decrementing or resetting the rekey counters.
Hence, there is a need for a carefully designed anonymous certificate revocation and replacement process to ensure that the anonymous certificate management system can achieve proper balances among critical objectives such as scalability, privacy, and performance.
The following defined terms are used throughout.
Anonymous Certificate: A certificate associated with a public-private key pair that, when used by vehicles, will not enable the identification and tracking of vehicles. In a combinatorial certificate scheme, each anonymous certificate will be shared among many vehicles in the VII system. The certificate is attached to a signed message that is generated by a vehicle and is used to verify the digital signature.
Anonymous Key: A private-public key pair that is shared among many vehicles in the VII system and is used to sign messages. Anonymous private keys are highly confidential and any compromise of an anonymous key can threaten the integrity of the VII system.
Attacker: Any entity that may be using anonymous keys and certificates to harm, damage, or manipulate the VII system either maliciously or unintentionally.
Attacker Elimination: The process of removal or rendering an attacker harmless to the VII system. Examples of attacker elimination include proactive system measures, such as locking out a vehicle (i.e., completely revoking all anonymous certificates on a vehicle), and pushing an attacker out of the system by means of certificate expiration.
Certificate: An electronic form of credential that uses a digital signature of a trustworthy authority to attest to the binding of a public key with an identity and/or a set of permissions.
Lock-out: An action taken by the VII system to deny certificate requests, typically because of excessive rekey attempts.
Private Application: An optional value-add service selected by the vehicle owner or occupant that is delivered using the VII system.
Private Key: An encryption/decryption code mathematically related to a paired public key in an asymmetric cryptographic system. A private key is held in secret and is used to decrypt information encrypted by its paired public key or sign information as proof of authenticity or integrity.
Public Application: A mandatory service in the VII system, generally for public safety or improved mobility, that all vehicles participate in using anonymous messages.
Public Key: An encryption code mathematically related to a paired private key in an asymmetric cryptographic system. A public key is shared and used to encrypt information that can only be decrypted by its paired private key. It is computationally infeasible to derive a private key from a public key.
Vehicle Segment: The collection of hardware and software installed in each vehicle that supports VII functions.